// https://leetcode.cn/problems/palindrome-partitioning/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 动态规划预处理所有回文子串
// 2. 回溯算法生成所有可能的分割方案
// 3. 在回溯中利用DP表快速判断子串是否为回文
// 4. 时间复杂度：O(n×2ⁿ)，空间复杂度：O(n²)

#include <iostream>
using namespace std;

#include <vector>
#include <string>
#include <algorithm>

class Solution 
{
public:
    vector<vector<string>> partition(string s) 
    {
        int m = s.size();

        vector<string> path;
        vector<vector<string>> ret;
        vector<vector<bool>> dp(m, vector<bool>(m, false));

        for (int i = m - 1 ; i >= 0 ; i--)
        {
            for (int j = i ; j < m ; j++)
            {
                if (s[i] == s[j])
                {
                    if (i == j)
                    {
                        dp[i][j] = true;
                    }
                    else if (i + 1 == j)
                    {
                        dp[i][j] = true;
                    }
                    else
                    {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
            }
        }

        dfs(0, s, path, dp, ret);

        return ret;
    }

    void dfs(int start, string& s, vector<string>& path, vector<vector<bool>>& dp, vector<vector<string>>& ret)
    {
        if (start == s.size())
        {
            ret.push_back(path);
            return ;
        }

        for (int end = start ; end < s.size() ; end++)
        {
            if (dp[start][end])
            {
                path.push_back(s.substr(start, end - start + 1));
                dfs(end + 1, s, path, dp, ret);
                path.pop_back();
            }
        }
    }
};

int main()
{
    string s1 = "aab", s2 = "a";
    Solution sol;

    auto vvs1 = sol.partition(s1);
    auto vvs2 = sol.partition(s2);

    for (const auto& vs : vvs1)
    {
        for (const auto& str : vs)
        {
            cout << str << " ";
        }
        cout << endl;
    }
    cout << endl;

    for (const auto& vs : vvs2)
    {
        for (const auto& str : vs)
        {
            cout << str << " ";
        }
        cout << endl;
    }
    cout << endl;

    return 0;
}